#include <iostream>
#include <vector>
using namespace std;
class Solution
{
    /**
     * @brief
     *  Given a positive integer, check whether it has alternating bits: namely,
     *  if two adjacent bits will always have different values.
     *
     */
public:
    /**
     * @brief
     * 1 <= n <= 2^31 - 1
     *
     * @param n
     * @return true 101
     * @return false 111 or 1011
     */
    bool hasAlternatingBits(int n)
    {
        vector<int> res(2, -1);
        while (n)
        {
            cout << (n & 1) << endl;
            res.pop_back();
            res.push_back(n & 1);
            n >>= 1;
            cout << "res:=>" << res[0] << res[1] << endl;
            if (res[0] == res[1])
            {
                return false;
            }
            else
            {
                int t = res[0];
                res[0] = res[1];
                res[1] = t;
            }
        }
        return true;
    }

    bool hasAlternatingBits_2(int n)
    {
        if (n == 1)
        {
            return true;
        }
        int begin = (n & 1);
        n >>= 1;
        while (n)
        {
            int end = n & 1;
            if (end == begin)
            {
                return false;
            }
            begin = end;
            n >>= 1;
        }
        return true;
    }

    bool hasAlternatingBits_3(int n)
    {
        return (n & (n >> 1)) == 0 && (n | (n >> 2)) == n;
    }
};
int main(int argc, char const *argv[])
{
    Solution s;
    cout << s.hasAlternatingBits(10) << endl;
    return 0;
}
